/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-06
 * Time: 0:11
 */
import java.util.*;
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }
}
public class Main{

    public static int i = 0;

    public static TreeNode createTree(String str){
        TreeNode root = null;
        if(str.charAt(i)!='#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else{
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            String str = sc.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
        }
    }

    /**
     *
     * @param root  根节点
     * @param node 指定的结点
     * @param stack  存放从根节点到指定结点的路径
     * @return
     */
    public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root==null || node==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean flag = getPath(root.left,node,stack);
        if(flag==true){
            return true;
        }
        flag = getPath(root.right,node,stack);
        if(flag==true){
            return true;
        }
        stack.pop();
        return false;
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1>size2){
            int size = size1-size2;
            while (size!=0){
                //出第一个栈里面的元素
                stack1.pop();
                size--;
            }
            while (!stack1.isEmpty() && !stack2.isEmpty()){
                //判断地址
                if(stack1.peek()==stack2.peek()){
                    return stack1.pop();
                }else {
                    stack1.pop();
                    stack1.pop();
                }
            }
        }else {
            int size = size2-size1;
            while (size!=0){
                //出第一个栈里面的元素
                stack1.pop();
                size--;
            }
            while (!stack1.isEmpty() && !stack2.isEmpty()){
                //判断地址
                if(stack1.peek()==stack2.peek()){
                    return stack1.pop();
                }else {
                    stack1.pop();
                    stack1.pop();
                }
            }
        }
        return null;
    }
}
